#pragma once
#include "LevelListNode.h"
/*
	此文件对外提供两个有用的模板类:VecList,LevelList和OrderedLevelList

	VecList:
		性能介于list和vector之间,比list好在可以更快的通过索引来访问
		比vector好在可以更快的以索引来删除插入
		应用场景:
			对一个表格数据增删查改后,要通过主键来

	LevelList:
		是一个完整的方案,功能类似StringIndexer


	OrderedLevelList:
		是一个完整方案,是一个可以快速查找,删除,插入并且维持有序的队列
		应用场景:
*/
namespace qb{
	namespace base{
		namespace container{
			template<typename Entry>
			class RootLevelNode{
			public:
			#if WIN32
				typedef typename LevelNode<Entry, RootLevelNode> NodeType;
				typedef typename DoubleLinkList<Entry> EntryQueue;
				typedef typename CachedObjectPool<NodeType> NodePool;
				typedef typename NodeType* NodePtr;
			#else
				typedef LevelNode<Entry, RootLevelNode> NodeType;
				typedef DoubleLinkList<Entry> EntryQueue;
				typedef CachedObjectPool<NodeType> NodePool;
				typedef NodeType* NodePtr;
			#endif 
			protected:
				NodeType	m_root;
				NodePool	m_node_pool;	// 
				EntryQueue	m_entry_queue;	// 全部Entry的队列;
				int			m_expect_count;	// 40
				int			m_max_count;	// 2.28*m_step_count
			public:
				RootLevelNode(int expectCount = 64) :m_expect_count(expectCount), m_max_count(0)
				{
					set_expect_count(expectCount);
				}
				~RootLevelNode(){ destroy(); }
				void set_expect_count(int expectCount){
					expectCount = expectCount <= 16 ? 16 : expectCount;
					m_expect_count = expectCount;
					m_max_count = (int)(m_expect_count*1.6);
				}
				Entry* destroy()
				{
					Entry* head = m_root.GetFirstEntry();
					DEBUG_ASSERT(head == m_entry_queue.GetHead());
					DEBUG_ASSERT(size() == m_entry_queue.GetCount());
					m_root.destroy(this);
					m_entry_queue.Reset();
					return head;
				}
			public:
				NodeType* Alloc(){ NodeType* node = m_node_pool.Alloc(); node->reset(); return node; }
				void Free(NodeType* node){ m_node_pool.Free(node); }
			public:
				bool check(bool recursive){ return recursive ? m_root.check_all() : m_root.check(); }
				void dump(){ m_root.dump(0); }
			public:
				int size()const{ return m_root.size(); }
				int append(Entry* e)
				{
					CHECK_SINGLE(e);
					Entry* last = at(size() - 1);
					NodePtr node = m_root.append_impl(e, last);
					m_entry_queue.Fix(nullptr, e, nullptr, true, size());
					m_root.balance(node, this, m_expect_count, m_max_count);
					return m_root.size() - 1;
				}
				int insert(Entry* e, int pos)
				{
					CHECK_SINGLE(e);
					if (pos < 0 || pos>m_root.size())return -1;
					if (pos == size())
					{
						return append(e);
					}
					Entry* cur = at(pos);
					NodePtr node = cur->GetNode();
					m_root.insert_impl(e, cur, node, this);
					m_entry_queue.Fix(nullptr, e, nullptr, true, size());
					DEBUG_ASSERT(at(pos) == e);
					m_root.balance(node, this, m_expect_count, m_max_count);
					DEBUG_ASSERT(at(pos) == e);
					return pos;
				}
				Entry*  at(int pos)
				{
					const NodeType* node = nullptr;
					if (pos < 0 || pos >= size())return nullptr;
					if (pos == 0){ return m_entry_queue.GetHead(); }
					else if (pos == size() - 1)return m_entry_queue.GetTail();
					Entry* e = m_root.at_impl(pos, node);
					return e;
				}
				Entry* erase(Entry* et, NodePtr node)
				{
					if (et)
					{
						DEBUG_ASSERT(node == et->GetNode() && node != nullptr);
						Entry* prev = et->GetPrev();
						Entry* next = et->GetNext();
						m_root.erase_impl(node, et, this);
						m_entry_queue.Fix(prev, et, next, false, size());
						m_root.balance(node, this, m_expect_count, m_max_count);
						return et;
					}
					return nullptr;
				}
				Entry* erase(int pos)
				{
					const NodeType* node = nullptr;
					Entry* et = m_root.at_impl(pos, node);
					NodeType* parent = et?et->GetNode():nullptr;
					return erase(et, parent);
				}
				int find(Entry* exist)
				{
					return m_root.find_impl(exist);
				}
				void print()const{}
			};


		}

		template<class Key>
		class LevelList{
			struct Entry;
			typedef typename container::RootLevelNode<Entry> RootNodeType;
			typedef typename RootNodeType::NodeType* NodePtr;
			struct Entry{
				Entry*	listprev;
				Entry*	listnext;
				Entry*	hashprev;
				Entry*	hashnext;
				Key		key;
				NodePtr	node;
			public:
				Entry() :listnext(nullptr), listprev(nullptr), key(), node(nullptr), hashprev(nullptr),hashnext(nullptr){}
				Entry* GetNext()const{ return listnext; }
				Entry* GetPrev()const{ return listprev; }
				NodePtr GetNode()const{ return node; }
				const Key& GetKey()const{ return key; }
				void SetNext(Entry* next){ listnext = next; }
				void SetPrev(Entry* prev){ listprev = prev; }
				void SetNode(NodePtr n){ node = n; };
				void reset(){
					listprev = listnext = nullptr;
					hashprev = hashnext = nullptr;
					node = nullptr;
					Key temp;
					std::swap(key, temp);
				}
			};
			#if WIN32
			typedef typename container::CachedObjectPool<Entry> EntryPool;
			typedef typename KeyHashMap<Entry, Key> EntryHashMap;
			typedef typename DoubleLinkList<Entry> EntryQueue;
			#else
			typedef container::CachedObjectPool<Entry> EntryPool;
			typedef KeyHashMap<Entry, Key> EntryHashMap;
			typedef DoubleLinkList<Entry> EntryQueue;
			#endif
			EntryHashMap	m_hashmap;
			RootNodeType	m_root;
			EntryPool		m_entry_pool;
			Key				m_blank;
		protected:
			Entry* erase_impl(const Key& k, unsigned int hash)
			{
				Entry* exist = m_hashmap.Remove(k, hash);
				if (exist)
				{
					exist->hashnext = exist->hashprev = nullptr;
					m_root.erase(exist,exist->GetNode());
				}
				return exist;
			}
		public:
			LevelList(int expectCount = 128) :m_root(expectCount)
			{
				m_hashmap.Build(GetHashPrimeLargerThan(expectCount));
			}
			~LevelList()
			{
				m_entry_pool.SetCapcity(1);
				clear();
			}
			void set_expect_count(int expectCount){ m_root.set_expect_count(expectCount); }
			typedef typename container::IteratorBase<Entry, Key> iterator;
			bool append(const Key& t)
			{
				unsigned int hash = t.GetHash();
				if (m_hashmap.Find(t, hash) != nullptr)
					return false;
				Entry* et = m_entry_pool.Alloc();
				et->key = t;
				m_root.append(et);
				m_hashmap.Insert(et, hash);
				return true;
			}
			bool append(Key&& t)
			{
				unsigned int hash = t.GetHash();
				if (m_hashmap.Find(t, hash) != nullptr)
					return false;
				Entry* et = m_entry_pool.Alloc();
				et->key = t;
				m_root.append(et);
				m_hashmap.Insert(et, hash);
				return true;
			}
			bool insert(const Key& k,int pos)
			{
				unsigned int hash = k.GetHash();
				/*Entry* efound = m_hashmap.Find(k, hash);
				if (efound && m_root.at(pos) == efound)
					return true;*/
				
				Entry* exist = erase_impl(k, hash);
				if (exist == nullptr)
				{
					exist = m_entry_pool.Alloc();
					exist->key = k;
				}

				m_hashmap.Insert(exist, hash);
				m_root.insert(exist,pos);
				return true;
			}
			bool erase(const Key& k)
			{
				unsigned int hash = k.GetHash();
				Entry* exist = erase_impl(k, hash);
				if (exist)
				{
					CHECK_SINGLE(exist);
					DEBUG_ASSERT(exist->hashprev == nullptr && exist->hashprev == nullptr);
					m_entry_pool.Free(exist);
					return true;
				}
				return false;
			}
			bool erase(int index)
			{
				Entry* exist = m_root.at(index);
				return exist ? erase(exist->key):false;
			}
			bool exist(const Key& k)
			{
				unsigned int hash = k.GetHash();
				return m_hashmap.Find(k, hash) != nullptr;
			}
			int  find(const Key& k)
			{
				unsigned int hash = k.GetHash();
				Entry* exist = m_hashmap.Find(k, hash);
				if (exist)
					return m_root.find(exist);
				return -1;
			}
			int  size()const{
				DEBUG_ASSERT(m_hashmap.GetCount() == m_root.size());
				return m_root.size();
			}
			const Key& at(int index)
			{
				Entry* et = m_root.at(index);
				return et ? et->GetKey() : m_blank;
			}
			void clear()
			{
				Entry* head = m_root.at(0);
				while (head)
				{
					Entry* temp = head;
					head = head->GetNext();
					DoubleLinkList<Entry>::Unlink(temp);
					temp->SetNode(nullptr);
					m_entry_pool.Free(temp);
				}
				m_hashmap.Clear();
				m_root.destroy();
			}
			void reserve(int n)
			{
				m_hashmap.Expand(n);
				n -= m_root.size();
				if (n > 0)m_entry_pool.Reserve(n);
			}
			iterator begin(){ return iterator(0, m_root.at(0)); }
			iterator end(){ return iterator(-1, nullptr); }
		};
	}//namespace base;
}//namespace ss;
